//
// Created by hitfy on 2018/4/22.
//
#include <bits/stdc++.h>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;//包含cv命名空间

vector<pair<int, int>> nodes;
vector<pair<int, int>> originNodes;

static int nodeSize = 5000;

void createRandomNodes() {
    set<pair<int, int>> nodeset;
    int times = 0;
    while(nodeset.size() < nodeSize){
        nodeset.insert(pair<int, int>(rand() % 100, rand() % 100));
        times++;
    }
    nodes.clear();
    originNodes.clear();
    copy(nodeset.begin(), nodeset.end(), back_inserter(nodes));
    copy(nodeset.begin(), nodeset.end(), back_inserter(originNodes));
    printf("The times of generating random points:%d\n", times);
}

void printNodes(vector<pair<int, int>> &nodes) {
    printf("nodes number:\t%ld\n", nodes.size());
    vector<pair<int, int>>::iterator it = nodes.begin();
    while (it != nodes.end()) {
        printf("(%d, %d), ", it->first, it->second);
        it++;
    }
    printf("\n");
}

void convexHull_Divide(vector<pair<int, int>> &nodes) {
    //点数小于等于3或者点全部在同一条x轴上直接返回
    if (nodes.size() <= 3 || nodes[0].first == nodes[nodes.size() - 1].first)
        return;
//    sort(nodes.begin(), nodes.end());
    //获取所有点在x轴上的中位数，并划分为两个子问题
    int x = nodes[nodes.size() / 2].first;
    vector<pair<int, int>> leftnodes, rightnodes;
    for (int i = 0; i < nodes.size(); i++) {
        if (nodes[i].first < x)
            leftnodes.push_back(nodes[i]);
        else
            rightnodes.push_back(nodes[i]);
    }
//    printf("Divide：%ld -> %ld + %ld\n", nodes.size(), leftnodes.size(), rightnodes.size());

    //递归调用
    //如果划分后有一个子问题空间为空，直接计算当前问题空间，否则对子问题进行递归调用
    if(!leftnodes.empty() && !rightnodes.empty()) {
        convexHull_Divide(leftnodes);
        convexHull_Divide(rightnodes);
        //合并子问题的解空间
        rightnodes.insert(rightnodes.begin(), leftnodes.begin(), leftnodes.end());
        nodes = rightnodes;
        sort(nodes.begin(), nodes.end());
//        printf("Merge：%ld + %ld -> %ld\n", leftret.size(), rightret.size(), nodes.size());
    }

    //参照Graham_Scan对（合并后的）解空间求解
    //求出Y坐标最小的p0
    int YMin = INT_MAX, point0 = 0;
    for(int i = 0; i < nodes.size(); i++){
        if(nodes[i].second < YMin){
            YMin = nodes[i].second;
            point0 = i;
        }
    }
    pair<int, int> point = nodes[point0];
//        printf("%d, %d\t%d, %d\n", point.first, point.second, nodes[0].first, nodes[0].second);
    //按照与point的极角排序
    set<pair<float, int>> polarset;//每个点与point0的极角的tan值和在原nodes集合中的位置
    for (int i = 0; i < nodes.size(); i++) {
        if (i == point0)
            continue;
        int x = nodes[i].first - point.first, y = nodes[i].second - point.second;
        polarset.insert(pair<float, int>((float) y / x, i));
    }
    //此时polarset的排序为负无穷到0再到正无穷，要调整为0到正无穷接着负无穷到0
//        printf("nodes number:\t%ld\n", polarset.size());
    set<pair<float, int>>::iterator tempit = polarset.begin();
    vector<pair<float, int>> polarvector;
    while (tempit != polarset.end()) {
        if (tempit->first < 0)
            polarvector.push_back(*tempit);
        else
            break;
        tempit++;
    }
    polarvector.insert(polarvector.begin(), tempit, polarset.end());
    stack<int> pointstack;
    vector<pair<float, int>>::iterator it = polarvector.begin();
    pointstack.push(point0);
    pointstack.push(it->second);
    int sectop = it->second;
    it++;
    pointstack.push(it->second);
    int top = it->second;
    it++;
    while (it != polarvector.end()) {
        int next = it->second;
        while ((nodes[sectop].first - nodes[next].first)
               * (nodes[top].second - nodes[next].second)
               - (nodes[sectop].second - nodes[next].second)
                 * (nodes[top].first - nodes[next].first) < 0) {
            pointstack.pop();
            top = pointstack.top();
            pointstack.pop();
            sectop = pointstack.top();
            pointstack.push(top);
//            printf("polar:%f, nodesindex:%d, top:%d, sectop:%d, next:%d size:%ld\n",
//                   it->first, it->second, top, sectop, next, nodes.size());
        }
        pointstack.push(next);
        sectop = top;
        top = pointstack.top();
        it++;
    }
    vector<pair<int, int>> retnodes;
    while (!pointstack.empty()) {
        retnodes.push_back(nodes[pointstack.top()]);
        pointstack.pop();
    }
//    printf("Return ");
//    printNodes(retnodes);
//    printf("%d -> %d, %d -> %d, %d -> %d\n", leftnodes.size(), leftret.size(),
//           rightnodes.size(), rightret.size(),
//           nodes.size(), retnodes.size());
    nodes = retnodes;
}

int main() {
    printf("Input Size(options:1000/2000/3000/4000/5000):");
    scanf("%d", &nodeSize);
    clock_t startTime, endTime;
    createRandomNodes();
    startTime = clock();
    convexHull_Divide(nodes);
    endTime = clock();
    printf("%ld\t%ld\t%ld\n", startTime, endTime, CLOCKS_PER_SEC);
    printf("Algorithm run time:\t%lfms\n", (double) (endTime - startTime) / CLOCKS_PER_SEC * 1000);
    printNodes(originNodes);
    printNodes(nodes);

    int w = 600;
    int pw = w / 100;
    Mat image(w, w, CV_8UC3, Scalar(255, 255, 255));
    //绘制网格
//    for(int i = 0; i < w/6; i++) {
//        line(image, Point(pw * i, 0), Point(pw*i, w), Scalar( 0, 0, 0 ));
//        line(image, Point(0, pw*i), Point(w, pw*i), Scalar( 0, 0, 0 ));
//    }
    for (int i = 0; i < originNodes.size(); i++)//绘制所有原始点并标为绿色
        circle(image, Point(originNodes[i].first * pw, originNodes[i].second * pw), 3, Scalar(0, 255, 0), -1, 8);
    for (int i = 0; i < nodes.size(); i++)//绘制凸包点并标为红色
        circle(image, Point(nodes[i].first * pw, nodes[i].second * pw), 3, Scalar(0, 0, 255), -1, 8);
    imshow("ConvexHull_Divide: " + to_string(nodeSize) + " points", image);
    waitKey();
    return 0;
}